翻訳と辞書
Words near each other
・ Back Where I Come From
・ Back Where It's At
・ Back Where You Started
・ Back with a Bong
・ Back with a Heart
・ Back with a Vengeance
・ Back with Basie
・ Back with the Thugz
・ Back with the Thugz Part 2
・ Back with Two Beasts
・ Back Yard Burgers
・ Back Yard Recordings
・ Back Young-chul
・ Back, Lewis
・ Back, Manitoba
Back-and-forth method
・ Back-arc basin
・ Back-arc region
・ Back-bond
・ Back-chaining
・ Back-end database
・ Back-face culling
・ Back-fire
・ Back-formation
・ Back-Fusion
・ Back-illuminated sensor
・ Back-of-the-envelope calculation
・ Back-off pattern
・ Back-On
・ Back-pass rule


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Back-and-forth method : ウィキペディア英語版
Back-and-forth method
In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular:
* It can be used to prove that any two countably infinite densely ordered sets (i.e., linearly ordered in such a way that between any two members there is another) without endpoints are isomorphic. An isomorphism between linear orders is simply a strictly increasing bijection. This result implies, for example, that there exists a strictly increasing bijection between the set of all rational numbers and the set of all real algebraic numbers.
* It can be used to prove that any two countably infinite atomless Boolean algebras are isomorphic to each other.
* It can be used to prove that any two equivalent countable atomic models of a theory are isomorphic.
* It can be used to prove that the Erdős–Rényi model of random graphs, when applied to countably infinite graphs, always produces a unique graph, the Rado graph.
* It can be used to prove that any two m-complete r.e. sets are recursively isomorphic.
== Application to densely ordered sets ==
Suppose that
* (''A'', ≤''A'') and (''B'', ≤''B'') are linearly ordered sets;
* They are both unbounded, in other words neither ''A'' nor ''B'' has either a maximum or a minimum;
* They are densely ordered, i.e. between any two members there is another;
* They are countably infinite.
Fix enumerations (without repetition) of the underlying sets:
:''A'' = ,
:''B'' = .
Now we construct a one-to-one correspondence between ''A'' and ''B'' that is strictly increasing. Initially no member of ''A'' is paired with any member of ''B''.
: (1) Let ''i'' be the smallest index such that ''a''''i'' is not yet paired with any member of ''B''. Let ''j'' be some index such that ''b''''j'' is not yet paired with any member of ''A'' and ''a''''i'' can be paired with ''b''''j'' consistently with the requirement that the pairing be strictly increasing. Pair ''a''''i'' with ''b''''j''.
: (2) Let ''j'' be the smallest index such that ''b''''j'' is not yet paired with any member of ''A''. Let ''i'' be some index such that ''a''''i'' is not yet paired with any member of ''B'' and ''b''''j'' can be paired with ''a''''i'' consistently with the requirement that the pairing be strictly increasing. Pair ''b''''j'' with ''a''''i''.
: (3) Go back to step (1).
It still has to be checked that the choice required in step (1) and (2) can actually be made in accordance to the requirements. Using step (1) as an example:
If there are already ''a''''p'' and ''a''''q'' in ''A'' corresponding to ''b''''p'' and ''b''''q'' in ''B'' respectively such that ''a''''p'' < ''a''''i'' < ''a''''q'' and ''b''''p'' < ''b''''q'', we choose ''b''''j'' in between ''b''''p'' and ''b''''q'' using density. Otherwise, we choose a suitable large or small element of ''B'' using the fact that ''B'' has neither a maximum nor a minimum. Choices made in step (2) are dually possible. Finally, the construction ends after countably many steps because ''A'' and ''B'' are countably infinite. Note that we had to use all the prerequisites.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Back-and-forth method」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.